package edu.qd.learn.day08;

/**
 * 二叉树
 *
 * @author 布衣
 */
public class BinaryTree {

    //根节点
    TreeNode root;

    public class TreeNode {
        TreeNode parent;
        int data;
        TreeNode left;
        TreeNode right;

        public TreeNode(int data) {
            this.data = data;
        }

        public TreeNode(TreeNode parent, int data) {
            this.parent = parent;
            this.data = data;
        }
    }

    /**
     * 添加一个节点
     */
    public void add(int data) {
        if (root == null) {
            root = new TreeNode(data);
            return;
        }
        findNodeForAdd(root,data);
    }

    /**
     * 递归方式查找节点
     */
    public void findNodeForAdd(TreeNode current, int target) {
        if (current.data > target) {
            if(current.left == null){
                current.left = new TreeNode(target);
            }else{
                findNodeForAdd(current.left, target);
            }
        } else {
            if(current.right == null){
                current.right = new TreeNode(target);
                return;
            }
            findNodeForAdd(current.right, target);
        }
    }

    /**
     * 先序遍历
     */
    public void prveOrder(TreeNode current){
        if(current == null){
            return ;
        }
        prveOrder(current.left);
        prveOrder(current.right);
        System.out.println(current.data);
    }

    public void prveOrder(){
        prveOrder(root);
    }

    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        bt.add(8);
        bt.add(13);
        bt.add(15);
        bt.add(11);
        bt.add(6);
        bt.add(3);

        bt.prveOrder();
    }

}
